class QuickSort():
    def __init__(self):
        self.count = 0
    def partition(self,arr,low,high):
        i = low - 1
        pivot = arr[high]
        for j in range(low,high):
            self.count+=1
            if arr[j] <= pivot:
                i+=1 # i记录的是比pivot小的元素的个数，保证low到i的元素值都比pivot小
                arr[i],arr[j] = arr[j],arr[i]
        arr[i+1],arr[high] = arr[high],arr[i+1]

        return (i+1)

    def sort(self,arr,low,high):
        if low<high:
            pi = self.partition(arr,low,high)

            self.sort(arr,low,pi-1)
            self.sort(arr,pi+1,high)

    # 判断是否有序
    def isSorted(self,ls):
        for i in range(1,len(ls)):
            if ls[i]<ls[i-1]:
                return False
        return True

